BM16 删除有序链表中重复的元素-II

https://www.nowcoder.com/practice/71cef9f8b5564579bf7ed93fbe0b2024

参考在题解：https://blog.nowcoder.net/n/7fdb6590c0a5407798a06df3ceb04199?f=comment

标准解法

func deleteDuplicates( head *ListNode ) *ListNode {
    first := &ListNode{
        Next: head, // 空节点插入链表头部
    }
    p := first
    for p.Next != nil && p.Next.Next != nil {
        // 存在重复的节点
        if p.Next.Val == p.Next.Next.Val {
            numFlag := p.Next.Val
            // 检查有多少个重复的
            for p.Next != nil && p.Next.Val == numFlag {
                p.Next = p.Next.Next
            }
        } else {
            p = p.Next
        }
    }
    return first.Next
}

23/5/10 暴力解法

用时 23分钟

暴力解法就是把插入到数组里面的 idx 记录到 Map 里面，如果出现过，则把那个位置打上特殊的标识，表示已经出现过了，最后再遍历一遍数组，把没有标识的节点重新插入到链表中

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    m := make(map[int]int)
    pre := head
    count := 0
    for pre != nil {
        count++
        pre = pre.Next
    }

    arr := make([]int, count)
    idx := 0
    for head != nil {
        if _, ok := m[head.Val]; !ok {
            m[head.Val] = idx
            arr[idx] = head.Val
        } else {
            arr[m[head.Val]] = 999
            arr[idx] = 999
        }
        idx++
        head = head.Next
    }

    dummy := new(ListNode)
    pre = dummy
    for i := range arr {
        if arr[i] != 999 {
            pre.Next = &ListNode{Val: arr[i]}
            pre = pre.Next
        }
    }

    return dummy.Next
}